package com.czk.sort;

import java.util.Arrays;

/**
 * 归并排序
 * @Author:ChenZhangKun
 * @Date: 2020/6/29 21:43
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] array={5,4,3,2,1,0};
        int[] temp=new int[array.length];
        mergeSort(array,0,array.length-1,temp);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 分治方法
     * @param array 原始数组
     * @param left 左边界
     * @param right 右边界
     * @param temp 临时数组
     */
    public static void mergeSort(int[] array,int left,int right,int[] temp){
        if (left<right){
            int mid=(left+right)/2; //中间索引
            // 向左递归分解
            mergeSort(array,left,mid,temp);
            // 向右递归分解
            mergeSort(array,mid+1,right,temp);
            // 合并
            merge(array,left,mid,right,temp);
        }
    }
    /**
     *
     * @param array 原始数组
     * @param left 左边界
     * @param mid 中间
     * @param right 右边界
     * @param temp 临时数组
     */
    public static void merge(int[] array,int left,int mid,int right,int[] temp){
        int i= left; //最左边的索引
        int j=mid+1; //最右边的索引
        int t=0; // 指向temp变量的当前索引
        // 先把左右两边的数据按规则拷贝到临时数组中，直到左右两边有序序列有一边处理完毕为止
        while (i<=mid&&j<=right){
            if (array[i]<=array[j]){
                // 左边有序序列的元素拷贝到临时数组
                temp[t]=array[i];
                i++;
                t++;
            }else {
                // 右边的有序序列元素拷贝到临时数组
                temp[t]=array[j];
                j++;
                t++;
            }
        }
        // 把剩余有数据一边依次填充到临时数组中
        // 左边有剩余，填充到临时数组
        while (i<=mid){
            temp[t]=array[i];
            t++;
            i++;
        }
        // 右边有剩余，填充到临时数组中
        while (j<=right){
            temp[t]=array[j];
            t++;
            j++;
        }

        // 将temp元素拷贝到array
        // 注意并不是每次都拷贝8个
         t=0;
        int tempLeft=left;
        while (tempLeft<=right){
            array[tempLeft]=temp[t];
            t++;
            tempLeft++;
        }
    }
}

